Introducion

1. Course Information
   • Abstract techniques
   • Master Recurrence
   • Complexity analysis
2. Logistics
   • Course portal
   • Discuss plateform
   • Grading
   • Training
3. C++
   • Definition
   • Why C++
   • Compagnies C++
   • First program
   • Second program
   • Why Data structures

Objectives

Welcome to the course Algorithms and Data structures. The objectifs of this course:

Gain deep knowlede on advanced algorithms and the zoology of data structure to solve different problems.

But What de we mean by a hard Problem. This is a list of problems in Computer Science sorted by their difficulty:

Computing the Shortes path.

Natural Language processing.

Imitation Driving in Self Driving cars. J.Zhou and al 2021

Course Objective

The goal if of course is not solve those advanced problems. Nevertheless, it is a mandatory step toward it.

We could resume the essential point of the course as follows:

1. Explore the abstract techniques to solve problems.
2. Master the notion of recurrence.
3. Get a intermediate grasp on data structures the their use for different situation.
4. Master the tool of algorithms analysis to compare the complexity of algorithms.

Abstract techniques

1. How to compute the expeceted distance between two random facebook usesrs.

This is a classical question in the Graph theory.

1. How to send an email between two cities:

We want to send an email between two countries or cities. We have a map of the connectec servers between those cities. But which server to choose. Thise is also a graph theory problem which uses rooting

Appreciate the power of recurrence

Recurence is a powerful technique that will allow you to tackle a large set of problems.

Image d'un arbre fractal, Si vous zoumer sur une partie de cette arbre, vous allez trouver la même image A fractal Image. The beauty of this image is if you zoom in any leaf of this tree. You'll see another tree.

Learn to analyse the complexity of your algorithms

One of the maine objectifs of this course it allow you to compare the complexity of a set of proposed algorithms. For example, let’s visit Sorting algorithms playground to appreciate the difference between a set of sorting algorithms.

Playground pour explorer la différence entre les algorithmes de tri.</b>

Logistics

Course portal

The main portal of the course is in the website:

It has :

1. Planning of the lectures.
2. Contents and useful links to visit ** before the lecture**.
3. Description of the Homeworks.
4. Collection o ressources pour le cours.

Discussion forum

We will use Piazza for all the discussions post lectures. You’ll be more than encouraged to actively participate in the form. Either to ask the questions to to respond to others.

We need our academic mail to register to the course.

Main plateform for discussion.

Grading

Your grade will be decided accordign the following the piechart:

Distribution of your grade.

The C++ language

Définition

The C++ language est an Object Oriented Progamming langauge. Its perferomances and **speed make is one the standard facto in programming languages. As a example, in the area of deep learning which needs a huge computation power, all the plateform library are written in C++.

Worldwide language popolarity comparison: Mar 2021 compared to a year ago

Here are some know courses that use C++ as its core languge:

1. Physics Based simulation Biological Structure.
2. Introduction to Cuda (Deep learning).
3. Introduction to Computer Networks
4. Convolutional Neural Networks
5. Parallel computing in Healthcare.
6. Medical Robotics.
7. Music computing design.
8. Signal processing models.

Why C++

Etant donné l’explosion et l’efficacité des réseaux de neurones. Tous les framework en base sont implémentés en C++ pour leur efficacité. Puis offrent des interfaces en des langages simples comme Python pour leur exploitation.

/*
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
    http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
==============================================================================*/

#include <vector>

#include "tensorflow/cc/framework/grad_op_registry.h"
#include "tensorflow/cc/framework/gradients.h"
#include "tensorflow/cc/ops/array_ops_internal.h"
#include "tensorflow/cc/ops/standard_ops.h"
#include "tensorflow/core/lib/strings/strcat.h"

namespace tensorflow {

REGISTER_NO_GRADIENT_OP("ShapeN");
REGISTER_NO_GRADIENT_OP("Rank");
REGISTER_NO_GRADIENT_OP("Size");

Status UnpackGrad(const Scope& scope, const Operation& op,
                  const std::vector<Output>& grad_inputs,
                  std::vector<Output>* grad_outputs) {
  int axis;
  TF_RETURN_IF_ERROR(GetNodeAttr(op.node()->attrs(), "axis", &axis));
  grad_outputs->push_back(Stack(scope, grad_inputs, Stack::Axis(axis)));
  return scope.status();
}

Compagnies that usesC++

Compagnies that uses C++

Companies that uses C++ at their core language.

Some projects written in C++

some harcore software that are written in C++

Projets in C++

Why this course uses C++

First program

To get our feet wet, let’s write a program to verfify if a numer is perfect.

A number is perfect if its equal to the sum of its divisor exluding itself.

for example the number \(6\) is perfect.

#include <iostream>  

//utiliser l'espace des nom std
using namespace std;

//Fonction pour vérifier si n est pafait
bool is_perfect( int n)
{
    auto S = 0;

    for(auto div=1; div <= n/2; div++)
        if ( n % div == 0)
            S += div;

    return S == n;
}

//fonction principale
int main(int argc, char *argv[])
{

    int count = 0;  //count des nombres parfaits

    int candidate = 1; //nombre à vérifier

    while( count < 3)
         {
             if(is_perfect( candidate ))
                {
                   cout<<candidate<<" ";                
                     count++;
                }
             candidate++;
         }
    //Retour à la ligne
    cout<<endl; 
    
    return 0;
}

Deuxième programme

/*tracer une distribution normale
 */

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>
#include <cmath>
 
int main()
{
    // Seed with a real random value, if available
    std::random_device r;
 
    // Choose a random mean between 1 and 6
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Randomly-chosen mean: " << mean << '\n';
 
    // Generate a normal distribution around that mean
    std::seed_seq seed2{r(), r(), r(), r(), r(), r(), r(), r()}; 
    std::mt19937 e2(seed2);
    std::normal_distribution<> normal_dist(mean, 2);
 
    std::map<int, int> hist;
    for (int n = 0; n < 10000; ++n) {
        ++hist[std::round(normal_dist(e2))];
    }
    std::cout << "Normal distribution around " << mean << ":\n";
    for (auto p : hist) {
        std::cout << std::fixed << std::setprecision(1) << std::setw(2)
                  << p.first << ' ' << std::string(p.second/200, '*') << '\n';
    }
}

Importance of Data structure

Mastering the tool of data structures is a must of each serious programmer. This mastery could help you choose the perfect mecanism to store data:

Let suppose that we want to write a program which group:

1. Add 100000 elements in the collection.
2. Try to find 10000 elements in the collection.
3. Delete 10000 in this collection

Here are the results for a different set of data structure. All the test are conducted in basic computer with 2.8GHz Inter core.